Article 7315

Title of the article

AUTOMATA-BASED DEFINITION OF CONTROL ALGORITHMS FOR PARALLEL PROCESSES IN THE READERSWRITERS PROBLEM BASED ON THE CONCEPT OF NON-DETERMINISM AND MONITOR MECHANISM

Authors

Vashkevich Nikolay Petrovich, Doctor of engineering sciences, professor, sub-department of computer engineering, Penza State University (40 Krasnaya street, Penza, Russia), vt@alice.pnzgu.ru
Volchikhin Vladimir Ivanovich, Doctor of engineering sciences, professor, President of Penza State University (40 Krasnaya street, Penza, Russia), cnit@pnzgu.ru
Biktashev Ravil' Aynulovich, Candidate of engineering sciences, professor, sub-department of computing machines and systems, Penza State Technological University (1a Baydukova lane, Penza, Russia), bra559620@sura.ru

Index UDK

681.3.012

Abstract

Background. The object of the study is processes and resources of control systems for parallel processing. The research subject is synchronization algorithms of concurrent processes in the readers-writers problem, based on the monitor mechanism. The aim of the study is to obtain a formal model of a synchronization algorithm that can be converted into a model of functional description of equipment, for example, using the VHDL language, with further implementation on FPGAs.
Materials and methods. Formalization of an algorithm of synchronization of parallel processes in the readers-writers problem was performed using a method based on the logic of nondeterministic automatons.
Results. The authors obtained formal description of an algorithm of process synchronization control in the readers-writers problem on the basis of using the monitor mechanism as a standard canonical system of recurrent equations, realizing all private events in the control algorithm. The description will be used for development of means of hardware support of a number of functions of multiprocessor operating systems, which include channels of interprocess sharing, message queues, etc. It will reducte latency and increase bandwidth means of communication, as well as their reliability and survivability due to thorough equipment debugging.
Conclusions. The obtained formal description allows, subsequently, simply to solve problems of structural implementation of control algorithms for processes and resources and verification of models, representing the main characteristics of the algorithm’s properties, which typically include security and liveliness, justice, presence
of mutual exclusions and other interacting processes.

Key words

control systems for processes and resources, interaction of parallel processes, process synchronization mechanisms, event non-deterministic machines, private event, formal description of an algorithm.

Download PDF
References

1. Khoar Ch. Vzaimodeystvuyushchie posledovatel'nye protsessy: per. s angl. [Communicating sequential processes: translation from English]. Moscow: Mir, 1989, 264 p.
2. Klark E. M., Grammberg O., Peled D. Verifikatsiya modeley programm: Model Checking: per. s angl. [Verification of program models: Model checking: translation from English]. Moscow: MTsNMO, 2002, 416 p.
3. Deytel Kh. M., Deytel P. Dzh., Chofnes D. R. Operatsionnye sistemy. Osnovy i printsipy: v 2 t.: per. s angl. [Operating systems. Basics and concepts: in 2 volumes: translation from English]. Moscow: Binom-Press, 2011, vol. 1, 1024 p.
4. Akgul B. E. S. and Mooney V. J. Design Automation and Test in Europe(DATE’01).2001,March,pp.633–639.
5. Biktashev R. A., Vashkevich N. P. Optiko-elektronnye pribory i ustroystva v sistemakh raspoznavaniya obrazov, obrabotki izobrazheniy i simvol'noy informatsii [Optoelectronic devices in systems of pattern recognition, image processing and symbolic information]. Kursk, 2015, pp. 42–44.
6. Vashkevich N. P., Biktashev R. A. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Tekhnicheskie nauki [University proceedings. Volga region. Engineering sciences]. 2011, no. 1 (7), pp. 3–11.
7. Hoare C. A. R. Commun. Of the ACM. 1974, Oct., vol. 17, pp. 549–557.
8. Brinch Hansen P. IEEE Trans. On Software Engineering. 1975, June, vol. SE-1, pp. 199–207.
9. Endryus G. R. Osnovy mnogopotochnogo parallel'nogo i raspredelennogo programmirovaniya: per. s angl. [Foundations of multithreaded, parallel and distributed programming: translation from English]. Moscow: Vil'yams, 2003, 512 p.
10. Tanenbaum E. Sovremennye operatsionnye sistemy [Modern operational systems]. 4th ed. Saint-Petersburg: Piter, 2015, 1120 p.
11. Vashkevich N. P. Nedeterminirovannye avtomaty v proektirovanii sistem parallel'noy obrabotki: ucheb. posobie [Non-deterministic automatons in parallel processing system design: tutorial]. Penza: Izd-vo PenzGU, 2004, 280 p.
12. Keylingert P. Elementy operatsionnykh sistem: per. s angl. [Operating system elements: translation from English]. Moscow: Mir, 1985, 296 p.
13. Vashkevich N. P., Biktashev R. A., Gurin E. I. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Ser. Tekhnicheskie nauki [University proceedings. Volga region. Engineering sciences]. 2007, no. 2, pp. 3–12.

 

Дата создания: 28.12.2015 13:36
Дата обновления: 28.12.2015 16:01